The approaches described in this section could be pursued, but are not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated herein, the approaches described in this section are not prior art to the claims in this application and are not admitted to be prior art by inclusion in this section.
An internet comprises a plurality of sites attached to a common network known as a backbone. Traffic between sites is routed from the source to a destination via nodes of the network. The traffic may be switched at the nodes based on the destination address. Alternatively, the traffic may be switched based on a header that is pre-pended to the original traffic such that some intermediate routing nodes have no knowledge of the final destination address. This latter approach is known as tunneling and one well-known use of this approach is in the provision of virtual private networks (VPNs). This application of tunneling will be used to exemplify the invention but the invention is not intended to be limited to this area of application.
The Internet Engineering Task Force (IETF) was set up to establish internet protocols. The IETF RFC2547 (March 1999) deals with the provision of VPN services by a service provider. At each site, there are one or more Customer Edge (CE) devices, each of which is attached via a data link (e.g. Ethernet, PPP, ATM, GRE tunnel etc.) to one or more Provider Edge (PE) routers. The service provider's network comprises the PE routers and as well as other routers (P routers) that are not attached to CE devices. When a service provider deploys an RFC2547-based VPN service, VPN traffic is transported across the core network between Provider-Edge routers (PE). This may be done by the use of IP “tunnels” which can be used to transport traffic across a service provider network. This idea was proposed by Eric Rosen and Yakov Rekhter in their IETF proposal entitled “Use of PE-PE GRE or IP in RFC2547 VPNs” (available from the IETF website and found at http://www.ietf.org/internet-drafts/draft-ietf-ppvpn-gre-ip-2547-01.txt).
According to RFC2547, each PE router maintains a number of forwarding tables. Each site to which the PE is attached is mapped to one of the forwarding tables. On receipt of a packet from a site, the forwarding table for that site is consulted to determine the route for the packet. Once a PE learns of a site that is reachable from a new site, this information is distributed to all the other PE routers to which the PE router is attached, for instance by using a protocol such as BGP (Border Gateway Protocol). The PE routers update their forwarding tables in response.
PE routers exchange VPNv4 routes using BGP. A PE router receives enough information in a VPNv4 update so as to determine that traffic received at a router, destined to some prefix P/m, should be tunneled to a destination N′. A PE router receiving this information must set up its forwarding path to do just this. IP based tunneling from one PE to another may be used as proposed in the Rosen/Rekhter draft referred to above. A logical IP tunnel network makes the endpoints of the tunnel, i.e. the PE routers, immediately adjacent at the internetwork layer—layer 3. Thus, an overlay network is used to represent the direct path taken by tunneled traffic. This overlay network is accessed by a PE router through a logical tunnel interface.
If traffic to P/m needs to be tunneled to some destination N′ (N′ being in the transport network), then the route to P/m is via N where N is an address on the tunnel overlay network and such that N is the tunnel address of a PE router reachable at N′ on the transport network.
In other words, for traffic to P/m to be tunneled to N′, an IP route of the form “P/m via N reachable through tunnel interface” is set up. The use of a tunnel interface and a tunnel overlay network allow routes in a routing table to prescribe how traffic should be routed without introducing exceptions for tunneled as opposed to forwarded traffic. The tunnel interface identifies that tunnel encapsulation must be imposed and N identifies which tunnel endpoint should be used.
When a routing update for the prefix P/m is received, the PE router needs to install the prefix P/m in the appropriate routing and forwarding table. A route lookup in this table for a destination covered by this prefix P/m should return the appropriate next hop/interface to which to dispatch the packet. To enable traffic to be transported over the tunnel overlay (i.e. tunneled through the transport network) to the remote PE, the route lookup must return a next hop on the overlay tunnel network. Consider the prefix 100.4.4.0/24 advertised by PE2 to PE1 with a next hop N, as shown in FIG. 1 and targeted to be installed in a table called “customer”. Assuming the correct route-targets are associated with the VPNv4 prefix in the BGP update, 100.4.4.0/24 would be installed in the routing and forwarding tables “customer” on PE1 as shown below:
ccassar-72a#sh ip route vrf customer
B 100.4.4.0/24 [200/0] via N, 00:01:47
The prefix 100.4.4.0/24 with next hop N must resolve through the connected tunnel network in order to ensure that traffic to 100.4.4.0/24 is tunneled through the transport network. Linking 100.4.4.0/24 to a next hop N on the tunnel interface completes the forwarding setup for traffic sent to 100.4.4.0/24. However, in the prior art, the IP address N on the tunnel would then have to be resolved to an underlying IP address of the router (123.1.1.4 in the example shown in FIG. 1) so that the outer IP header imposed when tunneling through the transport network can be populated appropriately and traffic can be tunneled to the destination through the transport network. This process is analogous to resolving an IP next hop address to a MAC address using ARP on an Ethernet interface.
The disadvantages of this solution include: the need to use an address resolution protocol to provide the mapping between the IP address of the tunnel endpoint in the overlay network and the underlying transport address; and the allocation of address space by a service provider for the tunnel network such that all tunnel endpoints are provided with unique addresses, which are distinct from those of the transport network. Address allocation and address resolution become more challenging if multiple service providers coordinate to provide the tunnel overlay network. In such a case, the overlay network is shared amongst all service providers and every router on the end of a tunnel is adjacent to every other one. Coordinating addressing and address resolution on the overlay network in such a case is more complicated if all addresses need to be unique amongst the set of addresses on the overlay AND the transport network.